//
// Created by buyongjiu on 2024/4/24.
//

#include <iostream>
#include <utility>
#include <stack>
#include <cassert>
#include "../include/LR.h"

void LR::build_LR_table() {
    this->V_map = grammar.V_map;
    auto startstate = new LR_struct();
    this->LR_table.push_back(startstate);
    this->state_struct[startstate->state] = startstate;
    auto startright = grammar.productions[grammar.V_map[start]][0];
    auto dot = new V(DOT, ".");
    this->V_map["."] = dot;
    startright.insert(startright.begin(), this->V_map["."]);
    auto end = new V(END, "#");
    this->V_map["#"] = end;
    Production_right start_Production_right = Production_right(startright, {end});
    this->addProduction(startstate, start, start_Production_right);
    this->get_closure(startstate);
    this->move(startstate);
    while (true) {
        int size = this->LR_table.size();
        for (int i = 0; i < this->LR_table.size(); i++) {
            this->move(this->LR_table[i]);
        }
        if (size == this->LR_table.size()) {
            break;
        }
    }

//    while(true) {
//        int size = this->LR_table.size();
//        for (int i = 0; i < this->LR_table.size(); i++) {
//            this->move(this->LR_table[i]);
//        }
//        if (size == this->LR_table.size()) {
//            break;
//        }
//    }
//    while (1) {
//        int size = this->LR_table.size();
//        for (auto &a: this->LR_table) {
//            this->get_closure(a, grammar);
//        }
////        while(1) {
////            int flag = 0;
////            for (auto &a: this->LR_table) {
////                int movesize = this->LR_table.size();
////                this->move(a);
////                if(movesize != this->LR_table.size()) {
////                    flag = 1;
////                    break;
////                }
////            }
////            if(flag == 0) {
////                break;
////            }
////        }
//        if (size == this->LR_table.size()) {
//            break;
//        }
//    }

//    for(auto & a: this->LR_table) {
//        std::cout<<"state "<<a->state<<std::endl;
//        for(auto & b: a->action) {
//            std::cout<<b<<std::endl;
//        }
//    }

}

void LR::addProduction(LR_struct *receive, const std::string &left, const Production_right &right) {
    for (auto &a: receive->action) {
        for (auto &b: a.right) {
            if (b == right && a.left == left) {
                return;
            }
        }
        if (a.left == left) {
            a.right.push_back(right);
            return;
        }
    }
    Production production = Production(left, {right});
    receive->action.push_back(production);
}

void LR::get_closure(LR_struct *state) {
    // 这个地方的size不该用action的数量 而应该是所有右部表达式的数量
    int size = 0;
    for (auto &pro: state->action) {
        for (auto &ri: pro.right) {
            size++;
        }
    }
    std::vector<Production> nowaction;
    // 开一个新的容器把之前的产生式放进去
    for (auto &production: state->action) {
        nowaction.push_back(production);
    }
    // 遍历这个容器的的同时，给需要添加的容器添加元素
    for (int i = 0; i < nowaction.size(); i++) {
        const auto &production = nowaction[i];
        const auto &right = production.right;
        for (int j = 0; j < right.size(); j++) {
            const auto &right1 = right[j];
            for (int k = 0; k < right1.right.size() - 1; k++) {
                if (right1.right[k]->type == DOT) {
                    if (right1.right[k + 1]->type == VN) {
                        std::string input = right1.right[k + 1]->name;
                        for (const auto &a: grammar.productions[grammar.V_map[input]]) {
                            auto newright = a;
                            newright.insert(newright.begin(), this->V_map["."]);
                            Production_right newPro = Production_right(newright, grammar.First[input]);
                            int haveequal = 0;
                            // 遍历之后的符号
                            for (int l = k + 2; l < right1.right.size(); l++) {
                                int flag = 0;
                                for (auto &fir: grammar.First[right1.right[l]->name]) {
                                    if (fir->name == "%") {
                                        flag = 1;
                                    }
                                        // 其他不为空的部分 也添加到向前搜索符中
                                    else {
                                        newPro.FSS.push_back(fir);
                                    }
                                }
                                if (flag == 1) {
                                    continue;
                                }
                                    // 没有的话 加入之后符号的first集
                                else {
                                    haveequal = 1;
                                    newPro.FSS = grammar.First[right1.right[l]->name];
                                    break;
                                }
                            }
                            // 之后无符号 照抄
                            if (haveequal == 0) {
                                newPro = Production_right(newright, right1.FSS);
                            }
                            addProduction(state, input, newPro);
                        }
                    }
                    break;
                }
            }
        }
    }
    int size_now = 0;
    for (auto &pro: state->action) {
        for (auto &ri: pro.right) {
            size_now++;
        }
    }
    if (size != size_now) {
        get_closure(state);
    }
}

void LR::move(LR_struct *nowstate) {
    for (int i = 0; i < nowstate->action.size(); i++) {
        auto &production = nowstate->action[i];
        auto &right = production.right;
        for (int j = 0; j < right.size(); j++) {
            auto &right1 = right[j];
            for (int k = 0; k < right1.right.size() - 1; k++) {
                if (right1.right[k]->type == DOT) {
                    std::string input = right1.right[k + 1]->name;
                    if (nowstate->next_state.find(input) == nowstate->next_state.end()) {
                        move_to(nowstate, input);   // moveto是当前状态和输入算下一状态
                    }
                    break;
                }
            }
        }
    }
}

void LR::move_to(LR_struct *nowstate, const std::string &input) {
    auto newstate = new LR_struct();
//    if (nowstate->state == 22 && newstate->state == 25) {
//        int a = 1;
//        // 29到46 exp 在46中只有一个产生式
//    }
    // 放在最外边，对于所有的产生式，一个输入应该只能产生一个状态
    for (int i = 0; i < nowstate->action.size(); i++) {
        auto &production = nowstate->action[i];
        auto &right = production.right;
        for (int j = 0; j < right.size(); j++) {
            auto &right1 = right[j];
            for (int k = 0; k < right1.right.size() - 1; k++) {
                // 找到了符合输入条件的产生式
                if (right1.right[k]->type == DOT && right1.right[k + 1]->name == input) {
                    // 将点后移产生新的产生式，放到新的状态之中
                    auto newright = right1;
                    newright.right[k] = newright.right[k + 1];
                    newright.right[k + 1] = this->V_map["."];
                    addProduction(newstate, production.left, newright);
                    break;
                }
            }
        }
    }
    // 所有循环完毕，那么新状态中已经加入了所有能移进的表达式
    // 取闭包 算出所有产生式
    this->get_closure(newstate);
    // 进行比较 确定该状态是否出现过
    int flag = 0;
    for (auto &a: this->LR_table) {
        if (compareState(a, newstate) == 1) {
            //出现过 让标号减一
            staticstate--;
            //把新状态删除
            delete newstate;
            newstate = a;
            flag = 1;
            // 不该return 出现过也应该有指向
        }
    }
    if (flag == 1) {
        nowstate->next_state[input] = newstate->state;
    } else {
        // 没有出现过，加入到LR表中
        nowstate->next_state[input] = newstate->state;

        this->LR_table.push_back(newstate);
        this->state_struct[newstate->state] = newstate;
    }
}

int LR::compareState(LR_struct *a, LR_struct *b) {
    if (a->action.size() == b->action.size()) {
        for (int i = 0; i < a->action.size(); i++) {
            auto &production1 = a->action[i];
            auto &right1 = production1.right;
            auto &production2 = b->action[i];
            auto &right2 = production2.right;
            if (production1.left != production2.left || right1.size() != right2.size()) {
                return 0;
            }
            for (int j = 0; j < right1.size(); j++) {
                auto &right11 = right1[j];
                auto &right22 = right2[j];
                if (right11.right.size() != right22.right.size()) {
                    return 0;
                }
                for (int k = 0; k < right11.right.size(); k++) {
                    if (right11.right[k]->name != right22.right[k]->name) {
                        return 0;
                    }
                }
                if (right11.FSS.size() != right22.FSS.size()) {
                    return 0;
                }
                for (int k = 0; k < right11.FSS.size(); k++) {
                    if (right11.FSS[k]->name != right22.FSS[k]->name) {
                        return 0;
                    }
                }
            }
        }
        return 1;
    }
    return 0;
}

int LR::build_GOTO_ACTION_Table() {
    for (auto &a: this->LR_table) {
        for (auto &b: a->action) {
            for (auto &c: b.right) {
                for (int i = 0; i < c.right.size(); i++) {
                    if (c.right[i]->type == DOT) {
                        if (i == c.right.size() - 1) {
                            if (b.left == start && c.FSS.size() == 1 && c.FSS[0]->name == "#") {
                                auto AC = new Action(ACC, "", {});
                                ACTION[a->state][c.FSS[0]->name] = AC;
                                break;
                            }
                            std::string left = b.left;
                            std::vector<V *> right = c.right;
                            right.pop_back();
                            auto FSS = c.FSS;
                            auto AC = new Action(REDUCE, left, right);
                            for (auto &d: FSS) {
                                ACTION[a->state][d->name] = AC;
                            }
                            break;
                        }
                        if (c.right[i + 1]->type == VT) {
                            auto AC = new Action(SHIFT, GO(a->state, c.right[i + 1]->name));
                            if (AC->num != -1) {
                                ACTION[a->state][c.right[i + 1]->name] = AC;
                            } else {
                                delete AC;
                            }
                        } else if (c.right[i + 1]->type == VN) {
                            int num = GO(a->state, c.right[i + 1]->name);
                            if (num != -1) {
                                GOTO[a->state][c.right[i + 1]->name] = num;
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}

int LR::accept(std::vector<Token> tokens) {
    std::vector<Token> token;
    for (auto &t: tokens) {
        if (t.type == OTHERS) {
            continue;
        } else if (t.type == ERROR) {
            std::string err = "lex error: ";
            err += t.value;
            std::cout << err << std::endl;
            return false;
        } else {
            token.push_back(t);
        }
    }
    token.push_back(Token(KEYWORD, 0, "#"));// 输入的结束
    int state = 0;
    std::stack<int> state_stack;
    std::stack<std::string> symbol_stack;
    state_stack.push(state);
    symbol_stack.push("#");
    int token_index = 0;
    while (true) {
        std::string input = token[token_index].value;
        print_State_Stack(state_stack);
        print_Symbol_Stack(symbol_stack);
        state = state_stack.top();
        if (ACTION[state].find(input) != ACTION[state].end()) {
            // 在ACTION表中找到对应项
            if (ACTION[state][input]->type == SHIFT) {
                state_stack.push(ACTION[state][input]->num);
                symbol_stack.push(input);
                token_index++;
            } else if (ACTION[state][input]->type == REDUCE) {
                auto production = ACTION[state][input];
                for (int i = 0; i < production->right.size(); i++) {
                    state_stack.pop();
                    symbol_stack.pop();
                }
                state = state_stack.top();
                symbol_stack.push(production->left);
                state_stack.push(GOTO[state][production->left]);
            } else if (ACTION[state][input]->type == ACC) {
                return 1;
            } else {
                std::cout << "error" << std::endl;
                return 0;
            }
        } else if (ACTION[state].find("%") != ACTION[state].end()) {
            state_stack.push(ACTION[state][input]->num);
            symbol_stack.push(input);
            token_index++;
        } else {
            std::cout << "token_index:" << token_index << std::endl;
            std::cout << "input:" << input << std::endl;
            return 0;
        }
    }
    return 0;
}

void LR::print_Action() {
    std::cout << "ACTION" << std::endl;
    for (auto &a: this->ACTION) {
        for (auto &b: a.second) {
            if (b.second->type == ACC) {
                std::cout << a.first << " -> " << b.first << " : " << "ACC" << std::endl;
            } else if (b.second->type == SHIFT) {
                std::cout << a.first << " -> " << b.first << " : " << "SHIFT" << b.second->num << std::endl;
            } else if (b.second->type == REDUCE) {
                std::cout << a.first << " -> " << b.first << " : " << "REDUCE" << b.second->left << " -> ";
                for (auto &d: b.second->right) {
                    std::cout << d->name << " ";
                }
                std::cout << std::endl;
            } else {
                std::cout << a.first << " -> " << b.first << " : " << "ERROR" << std::endl;
            }
        }
    }
}

void LR::print_GOTO() {
    std::cout << "GOTO" << std::endl;
    for (auto &a: this->GOTO) {
        for (auto &b: a.second) {
            std::cout << a.first << " -> " << b.first << " : " << b.second << std::endl;
        }
    }
}

int LR::GO(int nowstate, std::string input) {
    int nextstate;
    if (this->state_struct[nowstate]->next_state.find(input) != this->state_struct[nowstate]->next_state.end()) {
        nextstate = this->state_struct[nowstate]->next_state[input];
        return nextstate;
    }
    return -1;

}

void LR::print_Symbol_Stack(std::stack<std::string> temp_symbol_stack) {
    // 输出symbol_stack的内容
    std::cout << "symbol_stack: ";
    while (!temp_symbol_stack.empty()) {
        std::cout << temp_symbol_stack.top() << " ";
        temp_symbol_stack.pop();
    }
    std::cout << std::endl;
}

void LR::print_State_Stack(std::stack<int> temp_state_stack) {
    // 输出state_stack的内容
    std::cout << "state_stack: ";
    while (!temp_state_stack.empty()) {
        std::cout << temp_state_stack.top() << " ";
        temp_state_stack.pop();
    }
    std::cout << std::endl;
}
